﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace 华容道
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("求解开始");
            DateTime start = DateTime.Now;

            Aspect aspect = new();
            Queue<Aspect> queue = new();
            queue.Enqueue(aspect);
            HashSet<string> set = new();
            set.Add(aspect.ToString());

            bool over = false;

            while (queue.Any()&&!over)
            {
                Aspect now = queue.Dequeue();

                int[,] map = now.Map();
                var steps = now.Steps(map);

                foreach (var step in steps)
                {
                    Aspect next = new(now, step);
                    if (next.success)
                    {
                        Print(next);
                        over=true;
                        break;
                    }

                    string str = next.ToString();
                    if (set.Add(str))
                    {
                        queue.Enqueue(next);
                    }
                }

            }

            DateTime end = DateTime.Now;
            Console.WriteLine("求解结束");
            Console.WriteLine($"耗时:{(end - start).TotalMilliseconds}毫秒");
        }

        public static void Print(Aspect aspect)
        {
            if (aspect.parent != null)
            {
                Print(aspect.parent);
            }

            if (aspect?.step != null)
            {
                Console.WriteLine($"第{aspect.th}步:[{aspect.step.Item1},{aspect.step.Item2}]==>>{aspect.step.Item3}");
            }
        }
    }
}
